//92. 反转链表 II

#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode* next;
};
struct ListNode* reverse(struct ListNode* head) {
    struct ListNode* cur = head, * prev = NULL, * next = NULL;
    while (cur)
    {
        //头插法
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}
struct ListNode* reverseBetween(struct ListNode* head, int left, int right) {
    //1. 开辟临时头结点，接在头结点前
    //优点：不用分情况讨论
    struct ListNode* tmphead = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (NULL == tmphead)
    {
        perror("malloc fail:");
        return NULL;
    }
    tmphead->val = 0;
    tmphead->next = head;
 
    //2. 切割需要逆置的那一段
    struct ListNode* prev = tmphead;//保存leftNode前一个节点，后面链接的时候要用
    for (int i = 0; i < left - 1; i++)
    {
        prev = prev->next;
    }
    struct ListNode* leftNode = prev->next;
    struct ListNode* rightNode = tmphead;
    for (int i = 0; i < right; i++)
    {
        rightNode = rightNode->next;
    }
    struct ListNode* rightNext = rightNode->next;
    rightNode->next = NULL;//这里必须要置空

    //3. 逆置
    struct ListNode* res = reverse(leftNode);

    //4. 链接
    prev->next = res;
    leftNode->next = rightNext;//左节点是保存下来的，所以它就是逆置后的尾结点

    //5. 更新头结点，释放临时头结点
    head = tmphead->next;
    free(tmphead);
    return head;
}